D - XXOR

各桁を独立させて考える

上位のbitから決めていく

考察

XOR問題は各桁を独立させて考えられることが多いので、取り敢えず1と0だけ（1桁）で考えてみることにします…

0 1 1 1 1 1 0 0

この時、Xは0にすれば、0+1+1+1+1+1+0+0=5となり、最大になります。

0 0 1 0 0 0 1 0

Xを1にすると、1+1+0+1+1+1+0+1=6となり、最大になります。

0 0 1 1 0 0 1 1

X=1でもX=0でも総和は4でそれが答えです。

何個か例を挙げてみると、「0が半分より多かったら1とXORして反転させるけど、そうじゃなかったら0とXORする方が良い…」みたいなことが分かります。これが基本的な考え方になります。

次に、このような「XORで最大の〜」を求める時は、上位のbitから順に決めていくと良いことが多いので、上から順に決めていくとします。

上位のbitから決めていくんですが、K以上にならないためには「Kより先に1のbitを立てない」ことが必要になってきます。例を上げると、K=0001010なのにX=01…としちゃうとだめ、ということです。

まあここに書いてると超文字数を食うと思うので端的に言うと、「桁DP的思想を使って、未満が確定したか？のboolを取りながらXを上位bitから決めていく」という風になります。